#!/usr/bin/python3
# _*_ coding: utf-8 _*_
#
# Copyright (C) 2024 - 2024 heihieyouheihei, Inc. All Rights Reserved 
#
# @Time    : 2024/8/23 23:07
# @Author  : Yuyun
# @File    : leetcode_1047_删除字符串中的所有相邻重复项.py
# @IDE     : PyCharm


"""
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：
输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。
之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：
1 <= S.length <= 20000
S 仅由小写英文字母组成。
"""


class Solution:
    #   使用栈实现
    def remove_duplicates(self, s):
        stack = []
        for x in s:
            if not stack:
                stack.append(x)
                continue
            y = stack.pop()
            if x == y:
                continue
            else:
                stack.append(y)
                stack.append(x)
        result = ''
        # while stack:
        #     result += stack.pop()
        # result = result[::-1]
        for i in range(len(stack)):
            result += stack[i]
        return result
    #   栈代码优化
    def remove_duplicates_I(self,s):
        stack = []
        for x in s:
            #栈不为空，且最后一位与新元素相等时，推出
            if stack and stack[-1] == x:
                stack.pop()
            #其他情况（栈空或者不等），压入
            else:
                stack.append(x)
        return ''.join(stack)
    #   使用双指针模拟栈实现
    def remove_duplicates_II(self, s):
        stack = list(s)
        fast = slow = 0
        length = len(s)
        while fast < length:
            # 如果一样直接换，不一样会把后面的填在slow的位置
            stack[slow] = stack[fast]
            # 如果发现和前一个一样，就退一格指针
            if slow > 0 and stack[slow] == stack[slow - 1]:
                slow -= 1
            else:
                slow += 1
            fast += 1
        return ''.join(stack[:slow])


if __name__ == '__main__':
    s = input()
    solution = Solution()
    result = solution.remove_duplicates_II(s)
    print(result)